package cp;

/**
 * 爬楼梯
 * Created by 程程有小棉被啊 on 2020年12月10日.
 */
public class LeetCode_70 {
    
    /*
    假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
    注意：给定 n 是一个正整数。
    示例 1：
        输入： 2
        输出： 2
        解释： 有两种方法可以爬到楼顶。
        1.  1 阶 + 1 阶
        2.  2 阶

    示例 2：
        输入： 3
        输出： 3
        解释： 有三种方法可以爬到楼顶。
        1.  1 阶 + 1 阶 + 1 阶
        2.  1 阶 + 2 阶
        3.  2 阶 + 1 阶
    思路：
        假如此时需要爬到第5层，那么根据方法只能从第4层或者第3层爬，即第4层爬1阶，第5层爬2阶即可到达第5层。
        爬到第4层，则只能从第3层或者第2层爬，即第3层爬1阶，第2层爬2阶即可到达第4层。
        爬到第3层，则只能从第2层或者第1层爬，即第2层爬1阶，第1层爬2阶即可到达第4层。
        综上所述：爬到第5层的方法数 = 爬到第4层的方法数 + 爬到第3层的方法数
                爬到第4层的方法数 = 爬到第3层的方法数 + 爬到第2层的方法数
                f(5) = (f4) + f(3)
                f(4) = f(3) + f(2)
                ...
                f(n) = f(n-1) + f(n-2)  斐波那契数列公式
    方法：
        滚动数列即可。
        假设从第0层开始爬楼层依次递增，
        爬到第0层的方法只有1种
        爬到第1层的方法只有1种
        爬到第2层方法有2种
        爬到第3层方放3种
        爬到第4层方法5种
        爬到第5层方法8种
         X   Y   Z
         0   0   1          第0层
         0   1   1          第1层
         1   1   2          第2层
         1   2   3          第3层
         2   3   5          第4层
         3   5   8          第5层
         <--------顺着箭头一直往坐边挤，即可滚动数列
         说明:往左边滚动，可以看出，X的值会被Y替换，Y的值会被Z替换，Z的值=X+Y的和，其中Z的值即为爬到第N层的办法总数
     */


    public static void main(String[] args) {
        int num = 5;
        System.out.println(clamStaires(num));
    }

    static int clamStaires(int num) {
        int x = 0, y = 0, z = 1;//初始值，即第0层
        for (int i = 1; i <= num; i++) {
            x = y;
            y = z;
            z = x + y;
        }
        return z;
    }


}
